package com.ma.array;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @ClassName Solution870
 * @Author: mayongqiang
 * @DATE 2022/3/24 16:19
 * @Description: 优势洗牌
 */
public class Solution870 {
    /*
    给定两个大小相等的数组A和B，A 相对于 B 的优势可以用满足A[i] > B[i]的索引 i的数目来描述。
    返回A的任意排列，使其相对于 B的优势最大化。
        输入：A = [2,7,11,15], B = [1,10,4,11]
        输出：[2,11,7,15]

        输入：A = [12,24,8,32], B = [13,25,32,11]
        输出：[24,32,8,12]
     */
    public static void main(String[] args) {
        int[] nums1 = {2,7,11,15};
        int[] nums2 = {1,10,4,11};
        for (int i : advantageCount(nums1, nums2)) {
            System.out.print(i+",");
        }

    }

    public static int[] advantageCount(int[] nums1, int[] nums2) {
        //算法思想  找1中最大的和2中最大的比   1》2 则将1中最大的放前面  1《2则将最小的放前面
        int n = nums1.length;
        int[] res = new int[n];
        Arrays.sort(nums1);
        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (int[] p1, int[] p2) -> p2[1] - p1[1]
        );
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{i, nums2[i]});
        }
        int left = 0, right = n - 1;
        while (left <= right) {
            int[] p = pq.poll();
            int i = p[0], maxValue = p[1];
            if (nums1[right] > maxValue) {
                res[i] = nums1[right];
                right--;
            } else {
                res[i] = nums1[left];
                left++;
            }
        }
        return res;

    }
}
